
package ueb15;

//import java.util.Iterator;
//import java.util.LinkedList;
//
//
//
//import java.util.Iterator;
//import java.util.LinkedList;
//import java.util.List;


public class TreeImpl implements Tree {
	
    private NodeImpl root = (NodeImpl) createRoot();
    protected StringBuffer operationlog   = null;
        
    /**
    * returns the node with this iData
    * 
    * @param iData     iData of the node to find
    * @return          the node with this iData
    * @throws IllegalArgumentException  if iData is null
    */
    @Override
    public NodeImpl getNode(Object iData) throws IllegalArgumentException {
            if (iData == null) {
                    throw new IllegalArgumentException("Null einfuegen waere Schwachsinn!");
            }
    return getNode(root, iData);

    /*if(value==getRoot().getValue())
    {
        return root;
    }
    else
    {
                if(getNode(root, value).getValue()!=value)
                {
                        return null;
                }
                else
                {
                        return getNode(root, value);
                }
    }*/
    }

    /**
    * returns the root of the tree
    * 
    * @return root
    */
    @Override
    public NodeImpl getRoot() {
            return this.root;
    }

    /**
    * inserts iData at the right place
    * 
    * @param iData     that should be inserted
    * @return          operationlog
    * @throws IllegalArgumentException  if iData is null
    */
    @Override
    public String insertValue(Object iData, double dData) throws IllegalArgumentException {
        operationlog = null;
        if (iData == null) {
                throw new IllegalArgumentException("Null einfuegen waere Schwachsinn!");
        }
        /*if(value.equals(getNode(value)))//umsonst, da es nicht ordentlich vergleicht
        {
                return getNode(value);
        }*/
        return insertVal(root,iData,dData).toString();
    }
	
    private StringBuffer insertVal(NodeImpl current, Object iData, double dData) {
        if(current.isNil())
        {
            current.setiData(iData);
            operationlog.append(iData + "added \n");
            current.setLeftChild((NodeImpl) createNode(current));
            current.setRightChild((NodeImpl) createNode(current));

            repairInsertion(current);

            return operationlog;
        }

        if(((Comparable) iData).compareTo(current.getiData()) > 0)
        {
                return operationlog.append(insertVal(current.getRightChild(), iData, dData));
        }
        else if(((Comparable) iData).compareTo(current.getiData()) < 0)
        {
                return operationlog.append(insertVal(current.getLeftChild(), iData, dData));
        }
        else
        {
                return operationlog;
        }

        /*
        if(current.isNil())
        {

                createNode(current.getParent());
                current.setValue(value);
                if(value>current.getParent().getValue())
                {
                        current.getParent().setRightChild(current);

                }
                else
                {
                        current.getParent().setLeftChild(current);
                }
        }
        if(value>current.getValue())
        {
                current=current.getRightChild();
                insertVal(current, value);
        }
        else if(value<current.getValue())
        {
                current=current.getLeftChild();
                insertVal(current,value);
        }
        return current;*/
    }
	


    /**
    * calculates the size of the tree
    * 
    * @return size
    */
    @Override
    public int size() {
            NodeImpl snode=root;
            return sizehilf(snode);
    }
	
    private int sizehilf(NodeImpl snode) {	
            int size = 0;
            if((snode!=null)&&(snode.getiData()!=null))
            {
                    return (1+sizehilf(snode.getLeftChild())+sizehilf(snode.getRightChild()));
            }
            else
            {
                    return size;
            }
    }


    /**
    * Factory method to create new nodes.
    * 
    * @param node
    *            The parent node to create.
    * @return The newly created node.
    */
    protected NodeImpl createNode(NodeImpl node) {
            return new NodeImpl((NodeImpl) node);
    }

    /**
    * Factory method, that creates the root node.
    * 
    * @return The newly created root node, which is the only node without a
    *         parent.
    */
    protected NodeImpl createRoot() {
            return new NodeImpl(null);

    }


    /**
    * Repair the tree after the node has been inserted
    * 
    * @param node  The current node.
    */
    protected void repairInsertion(NodeImpl node) {

    }


    /**
    * Rotates the subtree of the given node left around that node.
    * 
    * @param nodeThe The node to <i>rotate</i> around.
    */
    protected void rotateLeft(NodeImpl node) {
        operationlog.append("rotate left" + node.getiData());
        /*NodeImpl nodeI=(NodeImpl)createNode(node);
        NodeImpl nodeII=(NodeImpl)createNode(node);
        //Zwischenspeicher
        if(!(node.isRoot()))
        {
                nodeI.setParent(node.getParent());
        }
        else
        {
                nodeI.setParent(null);
        }
        nodeI.setValue(node.getRightChild().getValue());
        if(node.getRightChild().isBlack())
        {
                nodeI.makeBlack();
        }
        else
        {
                nodeI.makeRed();
        }
        nodeI.setLeftChild(nodeII);
        nodeI.setRightChild(node.getRightChild().getRightChild());
        nodeII.setValue(node.getValue());
        if(node.isBlack())
        {
                nodeII.makeBlack();
        }
        else
        {
                nodeII.makeRed();
        }
        nodeII.setLeftChild(node.getLeftChild());
        nodeII.setRightChild(node.getRightChild().getLeftChild());
        //Aendern
        node.setLeftChild(nodeI.getLeftChild());
        node.setRightChild(nodeI.getRightChild());
        node.setParent(nodeI.getParent());
        if(nodeI.isBlack())
        {
                node.makeBlack();
        }
        else
        {
                node.makeRed();
        }
        if(nodeII.isBlack())
        {
                node.getLeftChild().makeBlack();
        }
        else
        {
                node.getLeftChild().makeRed();
        }
        node.setValue(nodeI.getValue());
        node.getLeftChild().setValue(nodeII.getValue());
        node.getLeftChild().setLeftChild(nodeII.getLeftChild());
        node.getLeftChild().setRightChild(nodeII.getRightChild());*/
        NodeImpl y=node;
        NodeImpl x=y.getRightChild();
        NodeImpl b = x.getLeftChild();
        x.setParent(y.getParent());
        if(!(y.isRoot()))
        {
                if(y.isLeftChild())
                {
                        y.getParent().setLeftChild(x);
                }
                else
                {
                        y.getParent().setRightChild(x);
                }
        }
        else
        {
                root=x;
        }
        x.setLeftChild(y);
        y.setRightChild(b);


    }

    /**
    * Rotates the subtree of the given node right around that node.
    * 
    * @param node  The node to <i>rotate</i> around.
    */
    protected void rotateRight(NodeImpl node) {
        operationlog.append("rotate right " + node.getiData());
        /*NodeImpl nodeI=(NodeImpl)createNode(node);
        NodeImpl nodeII=(NodeImpl)createNode(node);
        //Zwischenspeicher
        if(!(node.isRoot()))
        {
                nodeII.setParent(node.getParent());
        }
        else
        {
                nodeII.setParent(null);
        }
        nodeII.setValue(node.getLeftChild().getValue());
        if(node.getLeftChild().isBlack())
        {
                nodeII.makeBlack();
        }
        else
        {
                nodeII.makeRed();
        }
        nodeII.setLeftChild(node.getLeftChild().getLeftChild());
        nodeII.setRightChild(nodeI);
        nodeI.setValue(node.getValue());
        if(node.getLeftChild().isBlack())
        {
                nodeII.makeBlack();
        }
        else
        {
                nodeII.makeRed();
        }
        nodeI.setLeftChild(node.getLeftChild().getRightChild());
        nodeI.setRightChild(node.getRightChild());
        //Aendern
        node.setLeftChild(nodeII.getLeftChild());
        node.setRightChild(nodeII.getRightChild());
        node.setParent(nodeII.getParent());
        if(nodeII.isBlack())
        {
                node.makeBlack();
        }
        else
        {
                node.makeRed();
        }
        if(nodeI.isBlack())
        {
                node.getRightChild().makeBlack();
        }
        else
        {
                node.getRightChild().makeRed();
        }
        node.setValue(nodeII.getValue());
        node.getRightChild().setValue(nodeI.getValue());
        node.getRightChild().setLeftChild(nodeI.getLeftChild());
        node.getRightChild().setRightChild(nodeI.getRightChild());*/

        NodeImpl x=node;
        NodeImpl y=x.getLeftChild();
        NodeImpl b = y.getRightChild();
        y.setParent(x.getParent());
        if(!(x.isRoot()))
        {
                if(x.isLeftChild())
                {
                        x.getParent().setLeftChild(y);
                }
                else
                {
                        x.getParent().setRightChild(y);
                }
        }
        else
        {
                root=y;
        }
        y.setRightChild(x);
        x.setLeftChild(b);

    }

    /**
    * get the undernode with this iData
    * 
    * @param current   node under which you want to search
    * @param iData     iData to search
    * @return          node with iData
    */
    protected NodeImpl getNode(NodeImpl current, Object iData) {
            if(current.isNil())
            {
                    return null;
            }
            if(current.getiData()==null)
            {
                    return null;
            }
            if(((Comparable) iData).compareTo(current.getiData()) > 0 )
            {
                    current=getNode(current.getRightChild(), iData);
            }
            else if(((Comparable) iData).compareTo(current.getiData()) < 0)
            {
                    current=getNode(current.getLeftChild(),iData);
            }
            return current;
    }

    @Override
    public String toString() {
        return toHelpString(root);

    }
    
    private String toHelpString(NodeImpl current) {
        StringBuffer string = new StringBuffer("[");
//controller.addValue();

        if (current.getiData() == null){
            string.append(" null "); // TreeImpl is empty, so leave.
        }

        if (current.getLeftChild() != null) {
            toHelpString(current.getLeftChild());
            string.append(", ");
        }

        string.append(current.toString());

        if (current.getRightChild() != null) {
            string.append(", ");
            toHelpString(current.getRightChild());
            string.append("\t");
        }

        string.append("]");
        return string.toString();

    }
}